  Nessa se\c c\~ao \'e proposta uma meta-heur\'istica GRASP tradicional, com uma constru\c c\~ao gulosa e 
aleat\'oria seguida de uma busca local. 

O principal objetivo dessa se\c c\~ao \'e propor um modelo que divide uma busca local $NB(X)$ 
em parti\c c\~oes menores $NB_1(X), NB_2(X), ...,NB_n(X)$ de tal forma que
$NB(X) = NB_1(X) \cup NB_2(X) \cup ... \cup NB_n(X)$ e $NB_i(X) \cap NB_j(X) = \emptyset$ para todo par 
de vizinhan\c ca $(i,j)$. Esse modelo tenta ganhar a velocidade da busca local baseada na estrat\'egia 
$primeira\_melhora$ e a qualidade da solu\c c\~ao na estrat\'egia $melhor\_melhora$.
\subsection {Constru\c c\~ao}
   Nessa se\c c\~ao \'e apresentada a proposta de uma heur\'istica para constru\c c\~ao de uma solu\c c\~ao inicial para o problema PAGMGCP. Essa heur\'istica est\'a dividida em quatro etapas, que ser\~ao descritas no decorrer da se\c c\~ao. 
   
\begin{figure}[ht!]
\begin{center}
\small{
\fbox{
\begin{minipage}[b]{5.20 in}
\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\= \kill
\textbf{Procedimento} $\mathtt{Construcao(V,E)}$;\\
1\> $T \leftarrow \emptyset$ \\
2\> Criar grafo auxiliar $G_{aux}$ onde os vertices s\~ao os grupos\\
3\> $T \leftarrow T \cup Kruskal(G_{aux})$\\
4\> \textbf{Para\_todo} Grupo $g$ \textbf{fa\c ca};\\
5\>\> Conectar os vertices de $g \in V(T)$ usando a adapta\c c\~ao do Prim.\\
6\> \textbf{Fim\_Para\_todo}; \\
7\> $T \leftarrow T \cup \mathtt{Coleta\_Premio(T,E)}$\\
{\bf Fim}.
\end{tabbing}
\end{minipage}
}
}
\end{center}
\caption{Pseudo C\'odigo Constru\c c\~ao - Etapas 1 a 3}
\label{fig:pseudo_const1}
\end{figure}

   Na Figura~\ref{fig:pseudo_const1}, a primeira etapa (da linha 1 at\'e linha 3) consiste em conectar os grupos de v\'ertices. Para isso, foi aplicado um algoritmo de Kruskal adaptado, onde cada grupo foi tratado como um v\'ertice. As arestas inter-grupos foram ordenadas e as k melhores arestas, ou seja, as de menor custo, foram inclu\'idas em uma lista restrita de candidatos (RCL) para serem escolhidas aleatoriamente para entrar na solu\c c\~ao. 
   A segunda etapa \'e descrita da linha 4 \`a linha 6, na qual aplica-se uma adapta\c c\~ao do algoritmo Prim nos grupos que possuem mais de dois v\'ertices na solu\c c\~ao da primeira etapa. O crit\'erio de parada \'e conectar esses v\'ertices com o menor custo.
   Por fim, na linha 7 \'e feita a coleta de pr\^emio m\'inimo usando o algoritmo da Figura ~\ref{fig:pseudo_premio}.
   
\begin{figure}[ht!]
\begin{center}
\small{
\fbox{
\begin{minipage}[b]{5.20 in}
\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\= \kill
\textbf{Procedimento} $\mathtt{Coleta\_Premio(T,E)}$;\\
1\> \textbf{Enquanto} $Premio(T) < P_{min}$  \textbf{fa\c ca};\\
2\>\> Escolha uma aresta $(i,j) \in E$, onde $i \in V(T)$ e $j \notin V(T)$,\\
\>\>  com maior rela\c c\~ao:$\frac{min (p_j,premio\_restante)}{c_{ij}}$.\\
3\>\> $T \leftarrow T \cup \{(i,j)\} $\\
4\> \textbf{Fim\_Enquanto}; \\
{\bf Fim}.
\end{tabbing}
\end{minipage}
}
}
\end{center}
\caption{Pseudo C\'odigo Coleta de Pr\^emio}
\label{fig:pseudo_premio}
\end{figure}
   
   A coleta de pr\^emio do algoritmo da Figura~\ref{fig:pseudo_premio} descreve a terceira etapa, onde a partir de uma
solu\c c\~ao T, verifica-se se o pr\^emio m\'inimo foi atingido. Caso contr\'ario, \'e executado uma 
outra vers\~ao do algoritmo Prim, onde o v\'ertice escolhido \'e obtido pela seguinte f\'ormula:
  $\frac{min (p_j,premio\_restante)}{c_{ij}}$, onde $i \in V(T)$ e $j \notin V(T)$.
    O crit\'erio de parada \'e simplesmente atingir a soma m\'inima de pr\^emios. 

    
\begin{figure}[ht!]
\begin{center}
\small{
\fbox{
\begin{minipage}[b]{5.20 in}
\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\= \kill
\textbf{Procedimento} $\mathtt{Construcao\_2(T,V,E)}$;\\
1\> $E(T) \leftarrow \emptyset$ \\
2\> $E_{aux} \leftarrow \{(i,j) \in E$ $|$ $i \in V(T)$ e $j \in V(T)\}$ \\
3\> Criar grafo auxiliar $G_{aux}$ onde os vertices s\~ao os grupos\\
4\> $T \leftarrow T \cup Kruskal(G_{aux},E_{aux})$\\
5\> \textbf{Para\_todo} Grupo $g$ \textbf{fa\c ca};\\
6\>\> $T \leftarrow T \cup Kruskal(G,g,E_{aux})$\\
7\> \textbf{Fim\_Para\_todo}; \\
{\bf Fim}.
\end{tabbing}
\end{minipage}
}
}
\end{center}
\caption{Pseudo C\'odigo Constru\c c\~ao - Etapa 4}
\label{fig:pseudo_const2}
\end{figure}

    A Figura~\ref{fig:pseudo_const2} apresenta a quarta etapa. Inicialmente as arestas da solu\c c\~ao $T$ 
s\~ao descartadas na linha 1, e em seguida, na linha 2, somente as arestas em que os v\'ertices pertecem 
a solu\c c\~ao corrente s\~ao escolhidas para serem candidatas a entrarem na solu\c c\~ao final. Na linha 3, 
\'e criado um grafo auxiliar onde os v\'ertices s\~ao os grupos, para que na linha 4 o algoritmo $Kruskal$ 
seja executado nesse grafo considerando apenas as arestas em $E_{aux}$. Da linha 5 \`a linha 7, o mesmo \'e
feito para cada grupo, ou seja, os v\'ertices, que pertencem a $V(T)$, de cada grupo $g$ 
s\~ao conectados pelo algoritmo $Kruskal$.
 
\subsection {Busca Local}
  A vizinhan\c ca $NB(T)$ de uma solu\c c\~ao $T$ \'e formada pela remo\c c\~ao de um v\'ertice $i \in V(T)$ 
e adi\c c\~ao de um v\'ertice $j \notin V(T)$. Ap\'os feita a troca, o algoritmo da 
etapa 4 (ver Figura~\ref{fig:pseudo_const2}) \'e executado seguido pelo algoritmo de 
coleta de pr\^emio (ver Figura~\ref{fig:pseudo_premio}). Dessa forma temos o primeiro GRASP, chamado de 
GRASP-FULL.

  A segunda vers\~ao do GRASP, chamada de GRASP-PART2, trabalha com duas parti\c c\~oes de $NB(T)$, 
onde $NB_1(T)$ realiza apenas trocas de v\'ertices do mesmo grupo, ou seja, 
$NB_1(T) = $\{remo\c c\~ao de um v\'ertice $i \in V(T)$ e adi\c c\~ao de um v\'ertice $j \notin V(T)$ 
$|$ $grupo(i)=grupo(j)\}$. E a segunda parti\c c\~ao $NB_2(T)$ realiza apenas trocas de v\'ertices de 
grupos diferentes, ou seja, $NB_2(T) = $\{remo\c c\~ao de um v\'ertice $i \in V(T)$ e adi\c c\~ao 
de um v\'ertice $j \notin V(T)$ $|$ $grupo(i) \neq grupo(j)\}$. \'E f\'acil ver que 
$NB(T) = NB_1(T) \cup NB_2(T)$ e $NB_1(T) \cap NB_2(T) = \emptyset$.

  A terceira e \'ultima vers\~ao do GRASP, chamada de GRASP-PART3, trabalha com tr\^es parti\c c\~oes
de $NB(T)$, onde $NB_1(T)$ \'e exatamente a mesma do GRASP-PART2 e as outras duas s\~ao geradas a partir
da $NB_2(T)$ do GRASP-PART2. Para facilitar a explica\c c\~ao, suponha a divis\~ao do conjunto dos grupos
de v\'ertices $C$ em dois subconjuntos disjuntos $C_1$ e $C_2$, onde $\|C_1\|=\|C_2\|$. 
A $NB_2(T)$ do GRASP-PART3 realiza trocas entre v\'ertices de grupos diferentes 
onde o grupo do v\'ertice a ser adicionado pertence ao conjunto $C_1$, ou seja, 
$NB_2(T) = $\{remo\c c\~ao de um v\'ertice $i \in V(T)$ e adi\c c\~ao de um v\'ertice 
$j \notin V(T)$ $|$ $grupo(i) \neq grupo(j)$ e $ grupo(j) \in C_1\}$. E a terceira parti\c c\~ao $NB_3(T)$
do GRASP-PART3 realiza trocas entre v\'ertices de grupos diferentes 
onde o grupo do v\'ertice a ser adicionado pertence ao conjunto $C_2$, ou seja, 
$NB_3(T) = $\{remo\c c\~ao de um v\'ertice $i \in V(T)$ e adi\c c\~ao de um v\'ertice 
$j \notin V(T)$ $|$ $grupo(i) \neq grupo(j)$ e $ grupo(j) \in C_2\}$. \'E f\'acil ver que 
$NB(T) = NB_1(T) \cup NB_2(T) \cup NB_3(T)$, $NB_1(T) \cap NB_2(T) = \emptyset$, $NB_1(T) \cap NB_3(T) = \emptyset$ e $NB_2(T) \cap NB_3(T) = \emptyset$.


   
%    e suas fun\c c\~oes de custo $w(.)$ e pr\^emio $p(.)$, \cite{canuto:01} associa a 
%solu\c c\~ao $T(X)$ para o problema PCST a cada subconjunto $X \subseteq V$, definido pela \'arvore geradora 
%m\'inima induzida por $X$ no grafo $G$. $T_p(X)$ \'e obtido eliminando recursivamente de $T(X)$ todos os 
%v\'ertices com grau 1, onde a aresta incidente tem peso maior que seu pr\^emio.

%    A vizinha\c ca $N^{(1)}(X)$ da solu\c c\~ao $T(X)$ \'e formada por todas as \'arvores geradoras m\'inimas 
%$T(X^{'})$ tal que seu conjunto de v\'ertices $X^{'}$ difere de $X$ por exatamente 1 v\'ertice. A busca local 
%\'e baseada na estrutura de vizinhan\c ca $N^{(1)}(X)$ iniciando com uma solu\c c\~ao $T(X)$. O conjunto $X$ \'e 
%alterado iterativamente pela primeira melhora encontrada 
%ao explorar sua vizinha\c ca $N^{(1)}(X)$. O pseudo c\'odigo 
%da buscal local \'e apresentado na Figura ~\ref{fig:pseudo_bl}.
